package leetcode.dynamic;

import java.util.Arrays;

/**
 * @author: 26233
 * @create: 2022-03-26 23:29:55
 * @Description
 *
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 *
 * 返回 你可以获得的最大乘积 。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: n = 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 示例 2:
 *
 * 输入: n = 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 *  
 *
 * 提示:
 *
 * 2 <= n <= 58
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 *
 * 返回 你可以获得的最大乘积 。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: n = 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 示例 2:
 *
 * 输入: n = 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 *  
 *
 * 提示:
 *
 * 2 <= n <= 58
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 解法：
 *  1. 枚举几乎所有情况
 *  2. 3 * 3 > 2 * 2 * 2 一般情况是使用2，但是有的情况使用3的组合更好
 **/

public class LeetCode343_IntegerBreak {

    public int integerBreak(int n) {

        if(n == 2) return 1;

        int[] d = new int[n + 1];
        Arrays.fill(d, 1);

        for (int i = 3; i <= n; i++) {
            int s = 1;
            int e = i - 1;

            while (s++ <= e--){
                d[i] = Math.max(d[i], Math.max(s * d[e], Math.max(s * e, d[s] * d[e])));
            }
        }

        return d[n];
    }

    public static void main(String[] args) {

        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(4));
        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(5));
        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(6));
        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(7));
        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(8));
        System.out.println("r = " + new LeetCode343_IntegerBreak().integerBreak(9));

    }

}
